/**
 * @Name : hashTable
 * @Description : 封装哈希表
 * @Author : yi
 * @Date : 2022/3/30
 **/

/**
 * @description : 设计哈希函数，将传入的字符串哈希化，转换成 hashCode
 * @return : {number} hashCode
 * @param string 要哈希化的字符串 
 * @param limit 哈希表的最大个数（数组长度）
 **/
export function hashFn(string, limit = 7) {
	// 自己采用的一个质数（无强制要求，质数即可）
	const PRIME = 31;
    
	// 1.定义存储 hashCode 的变量
	let hashCode = 0;
    
	// 2.使用霍纳法则（秦九韶算法），计算 hashCode 的值
	for (let item of string) {
		hashCode = PRIME * hashCode +item.charCodeAt();
	}
    
	// 3.对 hashCode 取余，并返回
	return hashCode % limit;
}

/**
 * @description : 判断一个数是否为质数
 * @return : {boolean}
 * @param number
 **/
// 方法一，性能比较低
// export function isPrime(number) {
// 	// 1.如果传入的数小于 2，则直接返回 false
// 	if (number < 2) {
// 		return false;
// 	}
//
// 	// 2.如果传入的数大于等于 2，则循环判断
// 	for (let i = 2; i < number; i++) {
// 		if (number % i === 0) {
// 			return false;
// 		}
// 	}
//
// 	// 3.如果循环完毕，则说明该数为质数，返回 true
// 	return true;
// }

// 方法二，性能比较高
export function isPrime(number) {
	if (number <= 1 || number === 4) return false;

	const temp = Math.ceil(Math.sqrt(number));
	for (let i = 2; i <= temp; i++) {
		if (number % i === 0) {
			return false;
		}
	}

	// 3.如果循环完毕，则说明该数为质数，返回 true
	return true;
}

// 哈希表的封装
export class HashTable {
	constructor() {
		this.storage = [];  // 存储数据的数组
		this.count = 0; 	// 哈希表中的数据个数
		this.limit= 7;		// 哈希表的长度

		// 装填因子（已有个数/总个数）
		this.loadFactor = 0.75;
		this.minLoadFactor = 0.25;
	}

	// getPrime(number) 函数，获取一个质数
	getPrime(number) {
		while (!isPrime(number)) {
			number++;
		}
		return number;
	}

	//put(key, value) 函数，添加数据
	put(key,value) {
		// 1.根据 key 获取要映射的 storage 里面的 index (通过哈希函数获取)
		const index = hashFn(key, this.limit);

		// 2.根据 index 取出对应的bucket
		let bucket = this.storage[index];

		// 3.如果 bucket 为空，则创建一个新的 bucket
		if (!bucket) {
			bucket = [];
			this.storage[index] = bucket;
		}

		// 4.遍历 bucket，如果已经存在相同的 key，则更新 value
		for (let i =0; i < bucket.length; i++){
			let item = bucket[i];    //item 的格式为 [key, value]
			if (item[0] === key) {	 // 如果已经存在相同的 key，则更新 value
				item[1] = value;	 // 更新 value
				return;				 // 结束函数
			}
		}

		// 5.bucket 新增数据
		bucket.push([key,value]);  // bucket 存储元组 item ，格式是[key, value]
		this.count++;

		// 6.判断哈希表是否要扩容，若装填因子 > 0.75,则扩容
		if (this.count / this.limit > this.loadFactor) {
			this.resize(this.getPrime(this.limit * 2));
		}
	}

	// 重新调整哈希表大小，扩容或压缩
	resize(newLimit) {
		// 1.保存旧的 storage 数组内容
		const oldStorage = this.storage;

		// 2.重置所有属性
		this.storage = [];
		this.count = 0;
		this.limit = newLimit;

		// 3.遍历 oldStorage,取出所有数据，重新 put 到 this.storage
		for (const bucket of oldStorage) {
			if (bucket) {
				for (const b of bucket){
					this.put(b[0],b[1]);
				}
			}
		}
	}

	// 根据 get(key) 获取 value
	get(key) {
		const index = hashFn(key, this.limit);
		const bucket = this.storage[index];

		if (bucket === undefined) {
			return null;
		}

		for (const tuple of bucket) {
			if (tuple[0] === key) {
				return tuple[1];
			}
		}
		return null;
	}

	// remove(key) 删除指定 key 的数据
	remove(key) {
		const index = hashFn(key, this.limit);
		const bucket = this.storage[index];

		if (bucket === undefined) {
			return null;
		}

		// 遍历 bucket，找到对应位置的 tuple,将其删除
		for (let i = 0; i < bucket.length; i++) {
			const tuple = bucket[i];
			if (tuple[0] === key) {
				bucket.splice(i,1); //删除对应位置的数组项
				this.count--;

				// 根据装填因子的大小，判断是否要进行哈希表压缩
				if (this.limit > 7 && this.count / this.limit < this.minLoadFactor) {
					this.resize(this.getPrime(Math.floor(this.limit / 2)));
				}

				return tuple;
			}
		}
	}

	isEmpty() {
		return this.count === 0;
	}

	size() {
		return this.count;
	}

}